The present invention relates to computational methods for a computer to partition a combinatorial graph and, more particularly, a method for partitioning a weighted combinatorial graph using the eigenvalues and eigenvectors derived from the normalized Laplacian of the graph.
A variety of problems in computer science, statistics, and signal processing can be formulated as partitioning a weighted combinatorial graph. Examples include the segmentation of digital signals, i.e., decomposing a digital signal representative of audio [3], image [15], or volumetric data [7] into pieces (segments). For example, FIG. 1 is a pictorial illustration of partitioning a weighted combinatorial graph used for image segmentation. In FIG. 1, an overall image 10 contains an image of a dog that is to be segmented from the remainder of the overall image 10. The overall image 10 may be represented by a combinatorial graph 12. Combinatorial graphs are structures in which each pixel, or feature, in the image becomes a vertex in the graph. Neighboring vertices (pixels) are connected to one another with an edge. Each edge has a weight assigned to it that corresponds to the similarity of the pixels that edge connects. The construction of combinatorial graphs is known and not the subject of this disclosure. After the combinatorial graph is generated, partitioning of the graph may be performed along those edges between weakly related pixels on the theory that closely related pixels are from the same object while weakly related pixels may be from a different object. Of course, the problem is not that simple. For example, the dog in FIG. 1 could be a Dalmatian. In that case, we would not want each spot on the dog's coat to be identified as a new object. Putting aside such complexities for the moment, the partitioning of graph 12 produces the segmented image 14.
Graph partitioning plays a crucial role in many numerical algorithms, for example, in solving linear systems [16], partial differential equations [14], and physical simulation [14]. In statistics, graph partitioning is employed as a clustering tool [13] and in the analysis of mixing times of stochastic processes [10]. In the design of efficient algorithms, graph partitioning provides well-conditioned decompositions of the problem into pieces for divide-and-conquer methods [14]. In general, finding the best partitioning of a graph under some figure-of-merit results in a Non-deterministic Polynomial-time hard (NP-hard) mathematical optimization problem. In the applications mentioned above, the figures-of-merit fall into the quotient cut family of metrics. These metrics are minimized at the equilibrium between the cost associated with breaking edges in the graph and the balance in the relative sizes of the partitions. Such metrics, in the quotient cut family, seek equitable partitions of the graph.
Historically, graph partitioning methods have fallen into one of the three common paradigms: heuristic, linear and semi-definite programming, or spectral methods. Heuristic methods provide no quality guarantees on the solutions they generate in terms of a figure-of-merit. METIS [8] is an example of a heuristic partitioner. Heuristic methods tend to be fast and have found wide application in the implementation of divide-and-conquer style algorithms [14]. The two mathematical paradigms for approximating graph partitioning objective functions are 1) linear or semi-definite programming [19, 2, 12] and 2) spectral methods [5]. The methods in these two families provide guarantees on the cut quality in terms of a figure-of-merit. The LP/SDP-programming style methods suffer from a high polynomial time and memory complexity, limiting the size of the graphs they can partition. Spectral methods, while carrying weaker guarantees, can be applied to very large graphs while providing some guarantee on the quality.
The disclosed method is a novel spectral technique that empirically improves upon existing spectral algorithms for quotient cuts. Earlier spectral methods consisted of a two-stage algorithm. In the first stage, a small collection of, say k, eigenvectors of a graph Laplacian, with small eigenvalues, are computed. Each of these eigenvectors provides a real number for each vertex in the graph. Taken together, the eigenvectors provide a map for the graph vertices into . The vertices of the graph, now represented by points in space, are then clustered into a small collection of sets and these cluster memberships are taken to be the partition memberships for the graph [4]. This second stage is referred to as rounding, in which the continuous eigenvectors are mapped onto discrete partition indicator vectors. Recently, Lang and Rao have proposed a flow-based technique [11] that bests most geometric rounding methods for quotient 2-cuts of a graph. However, like geometric rounding methods, the hybrid method of Lang and Rao projects continuous solutions (such as eigenvectors) onto the feasible set in a single flow computation. This requires that the correct partition be well represented in the minimal eigenspace passed to the rounding step. Recent papers have exhibited graphs that do not satisfy this property [9].
The method disclosed herein replaces the direct rounding step (geometric or flow-based) with an iteration that reweights the graph in such a fashion that it eventually disconnects. Each iteration uses the eigenvalues and eigenvectors of the reweighted graph Laplacian to determine new edge weights. This iteration effects a rounding of the input vectors when the graph disconnects. By using the eigenvector from the previous iteration as a starting point for finding the new eigenvector, simple and efficient inverse powering methods converge in a small number of steps making the method computationally efficient.